package com.learn.algorithm_may_4;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * <p/>
 * 示例：
 * <p/>
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 * <p/>
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 * 说明：
 * <p/>
 * 给定的 n 保证是有效的。
 */
public class RemoveNthFromEnd {

    private static final Logger logger = LoggerFactory.getLogger(RemoveNthFromEnd.class);

    public static void main(String[] args) {
        new RemoveNthFromEnd().test();
    }

    public void test(){
        //- 准备单向链表
//        int[] arr = {1,2,3,4,5};
        int[] arr = {1,2};
        int n = 2;
        ListNode head = new ListNode(arr[0]);
        ListNode cursor = head;
        for (int i = 1; i < arr.length; i++) {
            cursor.next = new ListNode(arr[i]);
            cursor = cursor.next;
        }

        logger.info("输入：{}, {}", Arrays.toString(arr), String.format("[%s]", n));
        head = removeNthFromEnd(head, n);
        logger.info("输出：{}", head != null ? head.toString() : "[]");
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cursor = head;
        int length = 1;
        while (cursor.next != null){
            length++;
            cursor = cursor.next;
        }
        //- 这里注意，length-n-1 表示链表的倒数第n-1个节点，因为length >= n，所以length-n-1 可能为负数的
        int n_previous = length - n -1;
        //- 按当前题目length = -1，剔除第一个节点返回即可
        if (n_previous < 0){
            return head.next;
        }
        //- length非负数，再一次循环链表，直到倒数第n-1个节点，然后把它的next置为第n+1个节点
        cursor = head;
        while (n_previous > 0){
            n_previous--;
            cursor = cursor.next;
        }
        if (cursor.next == null){
            head = null;
        }else
            cursor.next = cursor.next.next;
        return head;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(val);
        ListNode cursor = next;
        while (cursor != null){
            builder.append(" -> " + cursor.val);
            cursor = cursor.next;
        }
        return builder.toString();
    }
}
